package sliding_window

//给定一个整数数组 arr，返回 arr的最大湍流子数组的长度。
//如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。
//
//更正式地来说，当 arr的子数组A[i], A[i+1], ..., A[j]满足仅满足下列条件时，我们称其为湍流子数组：
//若 i <= k < j：
//当 k为奇数时，A[k] > A[k+1]，且
//当 k 为偶数时，A[k] < A[k+1]；
//或 若i <= k < j：
//当 k 为偶数时，A[k] > A[k+1]，且
//当 k为奇数时，A[k] < A[k+1]。
//
//示例 1：
//输入：arr = [9,4,2,10,7,8,8,1,9]
//输出：5
//解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

//示例 2：
//输入：arr = [4,8,12,16]
//输出：2

//示例 3：
//输入：arr = [100]
//输出：1
//根据「减少」和「增加」交替出现的特点，规模较小的湍流子数组组成了规模较大的湍流子数组的长度，因此可以使用「动态规划」求解。

//状态定义：
//increased[i]：以 arr[i] 结尾，并且 arr[i - 1] < arr[i] 的湍流子数组的长度；
//decreased[i]：以 arr[i] 结尾，并且 arr[i - 1] > arr[i] 的湍流子数组的长度。

//状态转移方程：
//increased[i] = decreased[i - 1] + 1 if arr[i - 1] < arr[i] for i > 0；
//decreased[i] = increased[i - 1] + 1 if arr[i - 1] > arr[i] for i > 0。

//初始化：只有一个元素的时候，湍流子数组的长度是 1；
//输出：两个状态数组所有元素的最大值是最长湍流子数组的长度；
//空间优化：当前阶段状态只和上一个阶段【状态】有关，可以对【状态数组】进行重复利用。
func maxTurbulenceSizeDP(arr []int) int {
	res, l := 1, len(arr)
	if l < 2 {
		return l
	}

	//状态定义,初始化
	increased, decreased := make([]int, l), make([]int, l)
	increased[0] = 1
	decreased[0] = 1

	for i := 1; i < l; i++ {
		//状态转移
		if arr[i-1] < arr[i] {
			increased[i] = decreased[i-1] + 1 //「减少」和「增加」交替出现
			decreased[i] = 1
		} else if arr[i-1] > arr[i] {
			decreased[i] = increased[i-1] + 1 //「减少」和「增加」交替出现
			increased[i] = 1
		} else {
			increased[i] = 1
			decreased[i] = 1
		}

		res = max(res, max(increased[i], decreased[i]))
	}
	return res
}

func maxTurbulenceSizeSW(arr []int) int {
	left, right, ans := 0, 0, 1
	// expand window
	for right < len(arr)-1 {
		//特殊情况：窗口长度为1（即left和right相等的情况），只要arr[right] != arr[right+1]，就可以将right右移动一个单位。
		//否则，left和right都要同时移动
		if left == right {
			if arr[left] == arr[left+1] {
				left++ //left 和 right 同时移动
			}
			right++
		} else {
			if arr[right-1] < arr[right] && arr[right] > arr[right+1] {
				right++
			} else if arr[right-1] > arr[right] && arr[right] < arr[right+1] {
				right++
			} else {
				left = right
			}
		}
		ans = max(ans, right-left+1)
	}
	return ans
}

//双指针法
//由于湍流子数组是输入数组 连续 的子区间，【连续】很重要。
//可以遍历一次输入数组，记录上一个位置数值的变化是增加还是减少，只要上一个位置数值的变化与当前不同，当前得到湍流子数组的长度就加 1。在遍历的过程中，记录所有的湍流子数组的长度的最大值。
//根据此特点，我们可以设计两个变量，一前一后交替向右边移动，右边界先向右移动、左边界再向右边移动，经过一次遍历，得到最长湍流子数组的长度。
//时间复杂度：O(N)，NN 是输入数组的长度；
//空间复杂度：O(1)，只使用了常数个变量
func maxTurbulenceSize2P(arr []int) int {
	left, right, l, res := 0, 1, len(arr), 1
	if l < 2 {
		return l
	}

	pre := false
	for right < l {
		current := arr[right-1] < arr[right] //记录上一个位置的数值的变化
		if current == pre {                  //只要上一个位置数值的变化与当前不同
			left = right - 1
		}
		if arr[right-1] == arr[right] {
			left = right
		}
		right++
		res = max(res, right-left)
		pre = current
	}
	return res
}
